package leetcode.editor.template.dp.bag;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MultiPack {
    // 版本一：改变物品数量为01背包格式
    public void testMultiPack1() {
        List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
        List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
        List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
        int bagWeight = 10;
        int[] dp = new int[bagWeight + 1];

        // 转化为多个单一物品
        for (int i = 0; i < nums.size(); i++) {
            while (nums.get(i) > 1) {
                weight.add(weight.get(i));
                value.add(value.get(i));
                nums.set(i, nums.get(i) - 1);
            }
        }

        // 遍历0-1背包即可
        for (int i = 0; i < weight.size(); i++) {
            for (int j = bagWeight; j >= weight.get(i); j--) {
                dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
            }
            System.out.println(Arrays.toString(dp));
        }
    }

    // 版本二：改变遍历个数
    public void testMultiPack2() {
        List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
        List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
        List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
        int bagWeight = 10;
        int[] dp = new int[bagWeight + 1];

        for (int i = 0; i < weight.size(); i++) {
            for (int j = bagWeight; j >= weight.get(i); j++) {
                for (int k = 1; k < nums.get(i) && (j - k * weight.get(i)) >= 0; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight.get(i)] + k * value.get(i));
                }
            }
        }
    }
}
